import java.util.Random;
import java.util.Scanner;

public class Test {

    public static int fiblachi(int n) {
        if(n==1 || n==2) {
            return 1;
        }
        int sum = fiblachi(n-1) + fiblachi(n-2);
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(fiblachi(1));
        System.out.println(fiblachi(2));
        System.out.println(fiblachi(4));
    }

    public static int fanc3(int n) {
        int ret = 1;
        if (n > 1) {
            ret = n * fanc3(n-1);
        }
        return ret;
    }

    public static void main19(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(fanc3(n));
    }

    public static double sum1(double a,double b,double c) {
        return a + b + c;
    }

    public static int sum1(int a,int b) {
        return a + b;
    }

    public static void main18(String[] args) {
        System.out.println(sum1(10,20));
        System.out.println(sum1(25.1,58.0,54.6));
    }

    public static int fanc2(int n) {
        int ret = 0;
        if (n > 9) {
            ret = fanc2(n /10) + (n % 10);
        }
        if ( n<= 9){
            ret = n;
        }
        return ret;
    }

    public static void main17(String[] args) {
        int ret = fanc2(1729);
        System.out.println(ret);
    }

    public static int sum(int n) {
        int ret = 1;
        if (n > 1) {
           ret = n + sum(n-1);
        }
        return ret;
    }

    public static void main16(String[] args) {
        int ret = sum(10);
        System.out.println(ret);
    }

    public static void fanc1(int n) {
        if (n > 9) {
            fanc1(n / 10);
        }
        System.out.print(n % 10+" ");
        return;
    }

    public static void main15(String[] args) {
        fanc1(20458);
    }

    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }else {
            int f1 = 1;
            int f2 = 1;
            int f3 = 0;
            for (int i = 3; i <= n; i++) {
                f3 = f1 + f2;
                f1 = f2;
                f2 = f3;
            }
            return f3;
        }
    }

    public static void main14(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(40));
    }


    public static int max3(int a,int b,int c) {
        int tmp =max2(a,b);
        return max2(tmp,c);
    }

    public static int max2(int a,int b) {
        return  a > b ? a : b;
    }

    public static void main13(String[] args) {
        int num1 = max2(12,58);
        System.out.println(num1);
        int num2 = max3(54,97,15);
        System.out.println(num2);
    }

    public static void main12(String[] args) {
        System.out.println(fac(5));
    }

    public static int facNum(int n) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            int ret = fac(j);
            sum +=ret;
        }
        return sum;
    }

    public static int fac(int j) {
        int ret = 1;
        for (int i = 1; i <= j; i++) {
            ret *= i;
        }
        return ret;
    }

    public static void main11(String[] args) {
        int ret = facNum(5);
        System.out.println(ret);
    }

    public static void main10(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String password = "123456";
        int i = 0;
        for (; i < 3; i++) {
            String  n = scanner.nextLine();
            if (n.equals(password)) {
                System.out.println("登录成功！");
                break;
            }else {
                System.out.println("密码输入错误，请重新输入。");
            }
        }
        if (i == 3){
            System.out.println("密码输入错误超过三次，退出程序！");
        }
    }

    public static void main9(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int tmp = 0;
        while (n != 0) {
            tmp = n % 10;
            System.out.print(tmp+" ");
            n /= 10;
        }
    }

    public static void main8(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                System.out.print(i+"*"+j+"="+i*j+" ");
            }
            System.out.println();
        }
    }

    public static void main7(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = 1;
        double sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += a * (1.0 / i);
            a = -a;
        }
        System.out.println(sum);
    }

    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int tmp = 0;
        if (a % b == 0) {
            int min = 0;
            if (a > b) {
                min = b;
            }else {
                min = a;
            }
            System.out.println(min);
        }else {
            while (a % b != 0) {
                tmp = a % b;
                a = b;
                b = tmp;
            }
            System.out.println(tmp);
        }
    }

    public static void main5(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j || (i+j) == (n-1)) {
                        System.out.print("*");
                    }else {
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
    }

    public static void main4(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Random random = new Random();
        int num = random.nextInt(100);
        System.out.print("请输入你要猜的数字：");
        while (true) {
            int n = scanner.nextInt();
            if (n >num) {
                System.out.println("猜大了");
            }else if (n == num) {
                System.out.println("猜对了");
                break;
            }else {
                System.out.println("猜小了");
            }
        }

    }

    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.print("偶数位：");
        for (int i = 31; i >= 1; i-=2) {
            System.out.print(((n>>i) & 1)+ " ");
        }
        System.out.println();
        System.out.print("奇数位：");
        for (int i = 30; i >= 0 ; i-=2) {
            System.out.print(((n>>i) & 1)+ " ");
        }
    }

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;
        while (n != 0) {
            n = n & (n-1);
            count++;
        }
        System.out.println(count);
    }

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int count = 0;
            int tmp = i;
            while (tmp != 0) {
                tmp = tmp / 10;
                count++;
            }
             tmp = i;
            int sum = 0;
            while (tmp != 0) {
                 sum += Math.pow((tmp % 10),count);
                 tmp /= 10;
            }
            if (sum == i) {
                System.out.print(i+ " ");
            }
        }
    }
}
